package cn.bellychang.leetcode.question019;

/**
 * @author ChangLiang
 * @date 2020/11/2
 */
public class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode prev = null;
        ListNode curr = head;
        // 循环不变量 null->...->prev->curr 还没到Nth Node
        while (!isNthNode(curr, n)) {
            // 维持循环不变量
            prev = curr;
            curr = curr.next;
        }
        // 删除是head
        if (prev == null) {
            return head.next;
        } else {
            prev.next = curr.next;
            return head;
        }
    }

    /**
     * 判断是否是Nth Node
     * @param node
     * @param n
     * @return
     */
    private boolean isNthNode(ListNode node, int n) {
        for (int i = 0; i < n; i++) {
            node = node.next;
        }
        // 倒数第二个 就意味着这个Node进行两次next 其值为null
        return node == null;
    }
}
